#include <sys/timeb.h>
#include <fstream>
#include <limits>
// #include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <fcntl.h>
#include "util.h"

const uint32 kLogCacheSize = 1000;
uint64 * LOG_CACHE = NULL;
void InitLogCache() {
  LOG_CACHE = new uint64[kLogCacheSize];
  for (uint32 i=1; i<1000; i++)
    LOG_CACHE[i] = log(i) * 1000000;
}

// Global lock
pthread_mutex_t G_LOCK = PTHREAD_MUTEX_INITIALIZER;

// Constants we need
double TwoToTheMinus64 = pow(2.0, -64);
float NINF = -numeric_limits<float>::infinity();

uint64 RNG::RandomImportance(uint64 external) {
  if (external == 0) return 0;
  int log_external = (int) log(external) / log(2);
  uint64 r = Random();
  uint64 random_bit = ( (r ^ (r-1)) + 1 ) >> 1;
  return (( ((1 << log_external) - 1) | (random_bit << log_external) ) 
	  & 0x7fffffffffffffffull ) || 1;
}

uint64 BitCount(uint64 x) {
  x = (x & 0x5555555555555555ll) + ( (x & 0xAAAAAAAAAAAAAAAAll) >> 1);
  x = (x & 0x3333333333333333ll) + ( (x & 0xCCCCCCCCCCCCCCCCll) >> 2);
  x = (x & 0x0F0F0F0F0F0F0F0Fll) + ( (x & 0xf0f0f0f0f0f0f0f0ll) >> 4);
  x = (x & 0x00ff00ff00ff00ffll) + ( (x & 0xff00ff00ff00ff00ll) >> 8);
  x = (x & 0x0000ffff0000ffffll) + ( (x & 0xffff0000ffff0000ll) >> 16);
  x = (x & 0x00000000ffffffffll) + ( (x & 0xffffffff00000000ll) >> 32);
  return x;
}

int TestRandomImportance() {
  RNG rng;
  int x;
  int y;
  while (cin >> x >> y) {
    uint64 result = 0;
    for (int i=0; i<y; i++) {
      result |= rng.RandomImportance(x);
    }
    cout << (1 << BitCount(result)) << endl;
  }
  return 0;
}

// Computations in log space
float LnSum(float a, float b) {
  if (b>a) return LnSum(b, a);
  if (b == NINF) return a;
  return a + log(1 + exp(b-a)); 
}

// A version of += in logspace
void LnSumEq(float &a, float b) {
  float sum = LnSum(a, b);
  CHECK(finite(sum) || sum == NINF);
  a = sum; // LnSum(a, b); 
}

// LnFactorial. Cache first N values. Use Stirling's approx after
double * LN_FACTORIAL_CACHE = NULL;
double LnFactorial(uint32 n) {
  uint32 cache_size = 100;
  uint32 k = cache_size - 1;
  if (LN_FACTORIAL_CACHE == NULL) {
    LN_FACTORIAL_CACHE = new double[cache_size];
    LN_FACTORIAL_CACHE[0] = 0;
    for (uint32 c=1; c<cache_size; c++)
      LN_FACTORIAL_CACHE[c] = LN_FACTORIAL_CACHE[c-1] + log(c);
  }
  if (n < cache_size) return LN_FACTORIAL_CACHE[n];
  return (n * log(n) - n) - (k * log(k) - k) + LN_FACTORIAL_CACHE[k];
}

double RNG::RandomFraction() {
  return (Random()+ 0.5) * TwoToTheMinus64;
}

// vector of pairs of (i, v[i]) sorted by decreasing v[i]
// To make this faster, could use a allocated vector and delete it on the other
// side. Or pass in a vector to use.
vector<pair<int, float> > 
DecreasingSortWithIndices(const vector<float>& v) {
  vector<pair<int, float> > ret;
  for (uint32 i=0; i<v.size(); i++) ret.push_back(make_pair(i, v[i]));
  sort(ret.begin(), ret.end(), GreaterSecond<int, float>());
  return ret;
}

string Upcase(const string& s) {
  string ret = s;
  for (uint32 i=0; i<ret.size(); i++)
    ret[i] = toupper(ret[i]);
  return ret;
}

int UltimateDestination(const map<int, int> & m, int source) {
  const int * look = m % source;
  if (look) return UltimateDestination(m, *look);
  return source;
}

time_t OLD_TIME = time(0);
void PrintElapsedTime() {
  cout << "Elapsed time: " << (time(0) - OLD_TIME) << endl;
  OLD_TIME = time(0);
}

int GetMilliCount()
{
  // Something like GetTickCount but portable
  // It rolls over every ~ 12.1 days (0x100000/24/60/60)
  // Use GetMilliSpan to correct for rollover
  timeb tb;
  ftime( &tb );
  int nCount = tb.millitm + (tb.time & 0xfffff) * 1000;
  return nCount;
}

int GetMilliSpan( int nTimeStart )
{
  int nSpan = GetMilliCount() - nTimeStart;
  if ( nSpan < 0 )
    nSpan += 0x100000 * 1000;
  return nSpan;
}

int OLD_MILLI = GetMilliCount();

void ResetMilli() {
  OLD_MILLI = GetMilliCount();
}

void PrintElapsedTime2() {
  int new_milli = GetMilliCount();
  cout << "Elapsed time: " << new_milli - OLD_MILLI << endl;
  OLD_MILLI = new_milli;
}

void putback(istream & in, string s) {
  for (uint32 cc=0; cc < s.length(); cc++) {
    in.putback(s[s.length() - 1 - cc]);
    // cout << "putback " << s[s.length() - 1 - cc] << endl;
  }
}

string ReadLine (istream & in) {
  string ret;
  char c;
  while (in.get(c) && (c != '\n'))
    ret += c;
  // cout << "Reading about to return " << ret << "-----" << endl;
  return ret;
}

void ReadIntoString(string * res, istream& in) {
  char c;
  while (in.get(c))
    *res += c;
}

void ReadFileIntoString(string * res, string filename) {
  ifstream in(filename.c_str());
  ReadIntoString(res, in);
}

// TODO
bool IsSafeFileName(string filename) {
  return true;
}

bool Mmap(string filename, uchar ** block, int64 * length) {
  int fd = open (filename.c_str(), O_RDONLY);
  if (fd == -1) return false;
  struct stat st;
  stat(filename.c_str(), &st);
  int64 filesize = st.st_size;
  uchar * ret = (uchar *) mmap(0, filesize, PROT_READ, MAP_SHARED, fd, 0);
  *length = filesize;
  *block = ret;
  return true;
}

string itoa(int i) {
  ostringstream ostr;
  ostr << i;
  return ostr.str();
}

// compute k^n mod 2^32
uint64 UInt64Pow(uint64 k, uint64 n) {
  uint64 ret = 1;
  while (n) {
    if (n & 1) ret *= k;
    n >>= 1;
    k *= k;
  }
  return ret;
}

